package com.cn.codebrush.数组.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author Boolean
 * @Date 2022/4/20 18:04
 * @Version 1.0
 */
public class No15三数之和 {
    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        int[] nums1 = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};

        int[] nums2 = {-1,0,1,2,-1,-4};
        // -4,-1,-1,0,1,2
        int[] nums3 = {7,-10,7,3,14,3,-2,-15,7,-1,-7,6,-5,-1,3,-13,6,-15,-10,14,8,5,-10,-1,1,1,11,6,8,5,-4,0,3,10,-12,-6,-2,-6,-6,-10,8,-5,12,10,1,-8,4,-8,-8,2,-9,-15,14,-11,-1,-8,5,-13,14,-2,0,-13,14,-12,12,-13,-3,-13,-12,-2,-15,4,8,4,-1,-6,11,11,-7,-12,-2,-8,10,-3,-4,-6,4,-14,-12,-5,0,3,-3,-9,-2,-6,-15,2,-11,-11,8,-11,8,-7,8,14,-5,4,10,3,-1,-15,10,-6,-11,13,-5,1,-15};
        int[] nums4 = {34,55,79,28,46,33,2,48,31,-3,84,71,52,-3,93,15,21,-43,57,-6,86,56,94,74,83,-14,28,-66,46,-49,62,-11,43,65,77,12,47,61,26,1,13,29,55,-82,76,26,15,-29,36,-29,10,-70,69,17,49};

        System.out.println(threeSum2(nums2));
    }

    /**
     * 双指针
     * AC
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum2(int[] nums) {
        List reslist = new ArrayList();
        int n = nums.length;
        if(n==0 || n<3){
            return reslist;
        }

        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1]){continue;}
            if(nums[i] > 0){
                break;
            }
            int left = i+1;
            int right = n-1;

            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0){
                    reslist.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left < right && nums[left]==nums[left+1]){left++;}
                    while(left < right && nums[right-1]==nums[right]){right--;}
                    left++;
                    right--;
                }else if(sum > 0){
                    right --;
                }else if(sum < 0){
                    left ++;
                }
            }

        }
        return reslist;

    }


    /**
     * 回溯解法
     * 315 / 318 个通过测试用例
     */
    static List resList = new ArrayList();
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        threeSumHelper(nums,0,0,new ArrayList());
        return resList;

    }

    public static void threeSumHelper(int[] nums, int target, int t, List list) {
        if(target == 0 && list.size() == 3){
            resList.add(new ArrayList<>(list));
        }else if(list.size()>2){
            return;
        }
        for(int i=t;i<nums.length;i++){
            if(i>t && nums[i-1]==nums[i]){
                continue;
            }
            list.add(nums[i]);
            threeSumHelper(nums,target-nums[i],i+1,list);
            list.remove(list.size()-1);
        }

    }

}
